package leetcode.hot100;

import leetcode.tester.Tester;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.stream.Stream;

/**
 * 11. 盛水最多的容器
 * https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/13
 */
public class Hot5DbpMaxArea {
	public static void main(String[] args) throws IOException {
		int[] inp = null;
		try (Stream<String> lines = Files.lines(Paths.get("src/data/Hot5MaxArea.txt"))) {
			inp = lines
					.flatMap(line -> Arrays.stream(line.split(",")))
					.map(String::trim)
					.mapToInt(Integer::parseInt).toArray();
		} catch (IOException e) {
			e.printStackTrace();
		}
		Object[][] inputs = {
				new Object[]{new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}},
				new Object[]{new int[]{1, 1},},
				new Object[]{inp,},
		};
		Object[] outputs = {
				49,
				1,
				705634720
		};
		Tester.test(Tester.wrap(new Hot5DbpMaxArea()::maxArea), inputs, outputs);
		Tester.test(Tester.wrap(new Hot5DbpMaxArea()::maxAreaOpt), inputs, outputs);
		Tester.test(Tester.wrap(new Hot5DbpMaxArea()::maxAreaUltra), inputs, outputs);
	}

	/**
	 * 暴力法(超时)
	 */
	private Integer maxArea(int[] height) {
		int result = 0, n = height.length;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				int width = j - i;
				int area = width * Math.min(height[i], height[j]);
				result = Math.max(area, result);
			}
		}
		return result;
	}

	/**
	 * 双指针被定义为数组的前后两端, 只要让高度较小的那一侧向中间移动, 就可以在线性时间内求出最大的容量
	 */
	private Integer maxAreaOpt(int[] height) {
		int n = height.length;
		int l = 0, r = n - 1, result = 0;
		while (l != r) {
			result = Math.max((r - l) * Math.min(height[l], height[r]), result);
			if (height[l] < height[r]) {
				l++;
			} else {
				r--;
			}
		}
		return result;
	}

	/**
	 * 双指针被定义为数组的前后两端, 只要让高度较小的那一侧向中间移动, 就可以在线性时间内求出最大的容量
	 */
	private Integer maxAreaUltra(int[] height) {
		int n = height.length;
		int l = 0, r = n - 1, result = 0;
		while (l != r) {
			int lower = Math.min(height[l], height[r]);
			result = Math.max((r - l) * lower, result);
			while (l < r && height[l] <= lower) l++;
			while (l < r && height[r] <= lower) r--;
		}
		return result;
	}
}
